perm filename PHOUBL.TEX[ESS,JMC] blob
sn#562970 filedate 1981-02-12 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00035 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00005 00002
C00015 00003 We shall write
C00019 00004 We claim that this notion of $can$ is, to a first
C00025 00005 The notion of $can$ corresponding to the intuitive notion in
C00031 00006 For example, suppose a pair of Martians observe the situation
C00037 00007 In our opinion, this explains some of the difficulty
C00042 00008 \display 35pt: 2.: FORMALISM
C00047 00009 \yskip
C00051 00010 \display 61pt: { }: where we have adopted the convention that a quantifier
C00055 00011
C00060 00012 \noindent Here, $p$ is a person, $\sigma$ is an action or more generally a
C00065 00013 In the above program the external actions are represented by
C00069 00014 Therefore the formula that has to be proved may be written
C00074 00015 \noindent which expressed sufficient conditions for the ability of a person to
C00079 00016 \noindent and with this, the possibility of opening the safe can be proved.
C00083 00017 The present approach has a major technical advantage for
C00088 00018
C00094 00019
C00099 00020 A formal literature is like a formal language with a history:
C00105 00021 \display 35pt: 1.: Any consequence of sentences of $\sigma$ may be added.
C00110 00022 Many of the problems that give rise to the introduction of
C00115 00023 1. L. Fogel (1966) proposes to evolve intelligent automata
C00121 00024 It is interesting to compare the point of view of the present
C00127 00025
C00132 00026 \noindent By rule 2 of $M$ (which is present in almost all modal logics), since
C00138 00027 This semantic theory already provides an answer to the first
C00144 00028 $∀x . \Phi(x) → ∀x . exists(x,s) ⊃ \Phi(x,s)$
C00149 00029 Others of course may be needed when we add tenses and other
C00154 00030 $∀t$.$∀r$.$(cohistorical(r,t) ∧ cohistorical(t,s)) ⊃
C00160 00031
C00166 00032
C00169 00033
C00174 00034 \bib {{\bf Green, C. (1969)} Theorem-proving by resolution as a basis for
C00180 00035 \bib {{\bf Newell, A. & Ernst, C. (1965)} The search for generality.
C00184 ENDMK
C⊗;
\input macro.tex[let,jmc]
The interpretation of these equations is that the state of any
automaton at time $t+1$ is determined by its state at time $t$ and by
the signals received at time $t$. The value of a particular signal at
time $t$ is determined by the state at time $t$ of the automaton from
which it comes. Signals without a source automaton represent inputs
from the outside and signals without a destination represent outputs.
Finite automata are the simplest examples of systems that
interact over time. They are completely deterministic; if we know
the initial states of all the automata and if we know the inputs as a
function of time, the behaviour of the system is completely determined
by equations (1) and (2) for all future time.
The automaton representation consists in regarding the world
as a system of interacting subautomata. For example, we might regard
each person in the room as a subautomaton and the environment as
consisting of one or more additional subautomata. As we shall see,
this representation has many of the qualitative properties of
interactions among things and persons. However, if we take the
representation too seriously and attempt to represent particular
situations by systems of interacting automata, we encounter the
following difficulties:
\display 61pt: 1.: The number of states required in the subautomata is very
large, for example $2↑{10↑{10}}$, if we try to represent
someone's knowledge. Automata this large have to be
represented by computer programs, or in some other way
that does not involve mentioning states individually.
\display 61pt: 2.: Geometric information is hard to represent. Consider,
for example, the location of a multi-jointed object such
as a person or a matter of even more difficulty - the
shape of a lump of clay.
\display 61pt: 3.: The system of fixed interconnections is inadequate.
Since a person may handle any object in the room, an
adequate automaton representation would require signal
lines connecting him with every object.
\display 61pt: 4.: The most serious objection, however, is that (in our
terminology) the automaton representation is
epistemologically inadequate. Namely, we do not ever
know a person well enough to list his internal states.
The kind of information we do have about him needs to be
expressed in some other way.
Nevertheless, we may use the automaton representation for concepts of
{\sl can, causes,} some kinds of counterfactual statements (`If I had
struck this match yesterday, it would have lit') and, with some
elaboration of the representation, for a concept of {\sl believes.}
Let us consider the notion of {\sl can}. Let $S$ be a system of
subautomata without external inputs such as that of figure 2. Let
$p$ be one of the subautomata, and suppose that there are $m$ signal
lines coming out of $p$. What $p$ can do is defined in terms of a
new system $S↓p$, which is obtained from the system $S$ by
disconnecting the $m$ signal lines coming from $p$ and replacing them
by $m$ external input lines to the system. In figure 2, subautomaton
1 has one output, and in the system $S↓1$ this is replaced by an
external input. The new system $S↓p$ always has the same set of
states as the system $S$. Now let $π$ be a condition on the state
such as, `$a↓2$ is even' or `$a↓2\,=\,a↓3$'. (In the applications $π$ may
be a condition like `The box is under the bananas'.)
We shall write
\display 35pt: { }: $can(p,π,s)$
\noindent which is read, `The subautomaton $p$ {\sl can} bring about the condition
$π$ in the situation $s↑{\prime}$ if there is a sequence of outputs from the
automaton $S↓p$ that will eventually put $S$ into a state $a↑{\prime}$ that
satisfies $π(a↑{\prime})$. In other words, in determining what $p$ can
achieve, we consider the effects of sequences of its actions, quite
apart from the conditions that determine what it actually will do.
In figure 2, let us consider the initial state $a$ to be one
in which all subautomata are initially in state $0$. Then the
reader will easily verify the following propositions:
\display 35pt: 1.: Subautomaton 2 {\sl will} never be in state 1.
\display 35pt: 2.: Subautomaton 1 {\sl can} put subautomaton 2 in state 1.
\display 35pt: 3.: Subautomaton 3 {\sl cannot} put subautomaton 2 in state 1.
\yskip
---------- ---------- ----------
| | 1| | 3 | |
| |----→| |←----| |
| | | | | |
| 1 | | 2 | | 3 |
| | 2 | | | |
| |←----| | | |
| | | | | |
---------- ---------- ----------
\yskip
\ctrline{Figure 2. System $S$}
\yskip
$a↓1(t+1)=a↓1(t)+s↓2(t)$\par
$a↓2(t+1)=a↓2(t)+s↓1(t)+2↓{s↓3}(t)$\par
$a↓3(t+1)=\hbox{\bf if }a↓3(t)=0\hbox{\bf\ then }0\hbox{\bf\ else }a↓3(t)+1$\par
$s↓1(t)=\hbox{\bf if }a↓1(t)=0\hbox{\bf\ then }2\hbox{\bf\ else }1$\par
$s↓2(t)=\hbox{\bf 1 }$\par
$s↓3(t)=\hbox{\bf if }a↓3(t)=0\hbox{\bf\ then }0\hbox{\bf\ else }1$\par
|
---------- 1| ---------- 3 ----------
| | |-→| |←----| |
| | | | | |
| | | | | |
| 1 | | 2 | | 3 |
| | 2 | | | |
| |←-----| | | |
| | | | | |
---------- ---------- ----------
System $S↓1$
We claim that this notion of $can$ is, to a first
approximation, the appropriate one for an automaton to use internally
in deciding what to do by reasoning. We also claim that it
corresponds in many cases to the common sense notion of $can$ used in
everyday speech.
In the first place, suppose we have an automaton that decides
what to do by reasoning, for example suppose it is a computer using
an RP. Then its output is determined by the decisions it makes in
the reasoning process. It does not know (has not computed) in
advance what it will do, and, therefore, it is appropriate that it
considers that it can do anything that can be achieved by some
sequence of its outputs. Common-sense reasoning seems to operate in
the same way.
The above rather simple notion of $can$ requires some
elaboration both to represent adequately the commonsense notion and
for practical purposes in the reasoning program.
First, suppose that the system of automata admits external
inputs. There are two ways of defining $can$ in this case. One way
is to assert $can(p,π,s)$ if $p$ can achieve $π$ regardless of what
signals appear on the external inputs. Thus, instead of requiring
the existence of a sequence of outputs of $p$ that achieves the goal
we shall require the existence of a strategy where the output at any
time is allowed to depend on the sequence of external inputs so far
received by the system. Note that in this definition of $can$ we are
not requiring that $p$ have any way of knowing what the external
inputs were. An alternative definition requires the outputs to
depend on the inputs of $p$. This is equivalent to saying that $p$
can achieve a goal provided the goal would be achieved for arbitrary
inputs by some automaton put in place of $p$. With either of these
definitions $can$ becomes a function of the place of the subautomaton
in the system rather than of the subautomaton itself. We do not know
which of these treatments is preferable, and so we shall call the
first concept $cana$ and the second $canb$.
The idea that what a person can do depends on his position
rather than on his characteristics is somewhat counter-intuitive.
This impression can be mitigated as follows: Imagine the person to be
made up of several subautomata; the output of the outer subautomaton
is the motion of the joints. If we break the connection to the world
at that point we can answer questions like, `Can he fit through a
given hole?' We shall get some counter-intuitive answers, however,
such as that he can run at top speed for an hour or can jump over a
building, since these are sequences of motions of his joints that
would achieve these results.
The next step, however, is to consider a subautomaton that
receives the nerve impulses from the spinal cord and transmits them
to the muscles. If we break at the input to this automaton, we shall
no longer say that he can jump over a building or run long at top
speed since the limitations of the muscles will be taken into
account. We shall, however, say that he can ride a unicycle since
appropriate nerve signals would achieve this result.
The notion of $can$ corresponding to the intuitive notion in
the largest number of cases might be obtained by hypothesizing an
`organ of will,' which makes decisions to do things and transmits
these decisions to the main part of the brain that tries to carry
them out and contains all the knowledge of particular facts. If we
make the break at this point we shall be able to say that so-and-so
cannot dial the President's secret and private telephone number
because he does not know it, even though if the question were asked
could he dial that particular number, the answer would be yes.
However, even this break would not give the statement, `I cannot go
without saying goodbye, because this would hurt the child's
feelings'.
On the basis of these examples, one might try to postulate a
sequence of narrower and narrower notions of $can$ terminating in a
notion according to which a person can do only what he actually does.
This notion would then be superfluous. Actually, one should not look
for a single best notion of $can;$ each of the above-mentioned
notions is useful and is actually used in some circumstances.
Sometimes, more than one notion is used in a single sentence, when
two different levels of constraint are mentioned.
Besides its use in explicating the notion of $can,$ the
automaton representation of the world is very suited for defining
notions of causality. For, we may say that subautomaton $p$ caused
the condition $π$ in state $s$, if changing the output of $p$ would
prevent $π$. In fact the whole idea of a system of interacting
automata is just a formalization of the commonsense notion of
causality.
Moreover, the automaton representation can be used to
explicate certain counterfactual conditional sentences. For example,
we have the sentence, `If I had struck this match yesterday at this
time, it would have lit.' In a suitable automaton representation, we
have a certain state of the system yesterday at that time, and we
imagine a break made where the nerves lead from my head or perhaps at
the output of my `decision box', and the appropriate signals to
strike the match having been made. Then it is a definite and
decidable question about the system $S↓p$, whether the match lights
or not, depending on whether it is wet, etc. This interpretation of
this kind of counterfactual sentence seems to be what is needed for
RP to learn from its mistakes, by accepting or generating sentences
of the form, `had I done thus-and-so I would have been successful, so
I should alter my procedures in some way that would have produced the
correct action in that case'.
In the foregoing we have taken the representation of the
situation as a system of interacting subautomata for granted.
However, a given overall situation might be represented as a system
of interacting subautomata in a number of ways, and different
representations might yield different results about what a given
subautomaton can achieve, what would have happened if some
subautomaton had acted differently, or what caused what. Indeed, in
a different representation, the same or corresponding subautomata
might not be identifiable. Therefore, these notions depend on the
representation chosen.
For example, suppose a pair of Martians observe the situation
in a room. One Martian analyses it as a collection of interacting
people as we do, but the second Martian groups all the heads together
into one subautomaton and all the bodies into another. (A creature
from momentum space would regard the Fourier components of the
distribution of matter as the separate interacting subautomata.) How
is the first Martian to convince the second that his representation
is to be preferred? Roughly speaking, he would argue that the
interaction between the heads and bodies of the same person is closer
than the interaction between the different heads, and so more of an
analysis has been achieved from `the primordial muddle' with the
conventional representation. He will be especially convincing when
he points out that when the meeting is over, the heads will stop
interacting with each other, but will continue to interact with their
respective bodies.
We can express this kind of argument formally in terms of
automata as follows: Suppose we have an autonomous automaton $A$,
that is an automaton without inputs, and let it have $k$ states.
Further, let $m$ and $n$ be two integers such that $m,n≥k$. Now
label $k$ points of an $m$-$by$-$n$ array with The states of $A$.
This
can be done in $mn\choose k$! ways. For each of these ways we have a
representation of the automaton $A$ as a system of an $m$-state
automaton $B$ interacting with an $n$-state automaton $C$. Namely,
corresponding to each row of the array we have a state of $B$ and to
each column a state of $C$.The signals are in 1-1 correspondence
with the states themselves; thus each subautomaton has just as many
values of its output as it has states. Now it may happen that two of
these signals are equivalent in their effect on the other
subautomaton, and we use this equivalence relation to form
equivalence classes of signals. We may then regard the equivalence
classes as the signals themselves. Suppose then that there are now
$r$ signals from $B$ to $C$ and $s$ signals from $C$ to $B$. We ask
how small $r$ and $s$ can be taken in general compared to $m$ and
$n$. The answer may be obtained by counting the number of
inequivalent automata with $k$ states and comparing it with the
number of systems of two automata with $m$ and $n$ states
respectively and $r$ an $s$ signals going in the respective
directions. The result is not worth working out in detail, but tells
us that only a few of the $k$ state automata admit such a
decomposition with $r$ and $s$ small compared to $m$ and $n$.
Therefore, if an automaton happens to admit such a decomposition it
is very unusual for it to admit a second such decomposition that is
not equivalent to the first with respect to some renaming of states.
Applying this argument to the real world, we may say that it is
overwhelmingly probable that our customary decomposition of the world
automaton into separate people and things has a unique, objective and
usually preferred status. Therefore, the notions of $can$ of
causality, and of counterfactual associated with this decomposition
also have a preferred status.
In our opinion, this explains some of the difficulty
philosophers have had in analysing counterfactuals and causality. For
example, the sentence, `If I had struck this match yesterday, it
would have lit' is meaningful only in terms of a rather complicated
model of the world, which, however, has an objective preferred
status. However, the preferred status of this model depends on its
correspondence with a large number of facts. For this reason, it is
probably not fruitful to treat an individual counterfactual
conditional sentence in isolation.
It is also possible to treat notions of belief and knowledge
in terms of the automaton representation. We have not worked this
out very far, and the ideas presented here should be regarded as
tentative. We would like to be able to give conditions under which
we may say that a subautomaton $p$ believes a certain proposition.
We shall not try to do this directly but only relative to a predicate
$B↓p(s,w)$. Here $s$ is the state of the automaton $p$ and $w$ is
a proposition; $B↓p(s,w)$ is true if $p$ is to be regarded as
believing $w$ when in state $s$ and is false otherwise. With respect
to such a predicate $B$ we may ask the following questions:
\display 35pt: 1.: Are $p$'s beliefs consistent? Are they correct?
\display 35pt: 2.: Does $p$ reason? That is, do new beliefs arise that are
logical consequences of previous beliefs?
\display 35pt: 3.: Does $p$ observe? That is, do true propositions about
automata connected to $p$ cause $p$ to believe them?
\display 35pt: 4.: Does $p$ behave rationally? That is, when $p$ believes a
sentence asserting that it should do something does $p$
do it?
\display 35pt: 5.: Does $p$ communicate in language $L$? That is, regarding
the content of a certain input or output signal line as
in a text in language $L$, does this line transmit
beliefs to or from $p$?
\display 35pt: 6.: Is $p$ self-conscious? That is, does it have a fair
variety of correct beliefs about its own beliefs and the
processes that change them?
It is only with respect to the predicate $B↓p$ that all these
questions can be asked. However, if questions 1 thru 4 are answered
affirmatively for some predicate $B↓p$, this is certainly
remarkable, and we would feel fully entitled to consider $B↓p$ a
reasonable notion of belief.
In one important respect the situation with regard to belief
or knowledge is the same as it was for counterfactual conditional
statements: no way is provided to assign a meaning to a single
statement of belief or knowledge, since for any single statement a
suitable $B↓p$ can easily be constructed. Individual statements
about belief or knowledge are made on the basis of a larger system
which must be validated as a whole.
\yyskip
\display 35pt: 2.: FORMALISM
\yskip
\noindent In part 1 we showed how the concepts of ability and belief could be
given formal definition in the metaphysically adequate automaton
model and indicated the correspondence between these formal concepts
and the corresponding commonsense concepts. We emphasized, however,
that practical systems require epistemologically adequate systems in
which those facts which are actually ascertainable can be expressed.
In this part we begin the construction of an
epistemologically adequate system. Instead of giving formal
definitions, however, we shall introduce the formal notions by
informal natural-language descriptions and give examples of their use
to describe situations and the possibilities for action they present.
The formalism presented is intended to supersede that of McCarthy
(1963).
\yyskip
\noindent {\bf Situations}
\yskip
A situation $s$ is the complete state of the universe at an instant
of time. We denote by $Sit$ the set of all situations. Since the
universe is too large for complete description, we shall never
completely describe a situation; we shall only give facts about
situations. These facts will be used to deduce further facts about
that situation, about future situations and about situations that
persons can bring about from that situation.
This requires that we consider not only situations that
actually occur, but also hypothetical situations such as the
situation that would arise if Mr. Smith sold his car to a certain
person who has offered $\$250$ for it. Since he is not going to sell
the car for that price, the hypothetical situation is not completely
defined; for example, it is not determined what Smith`s mental state
would be and therefore it is also undetermined how quickly he would
return to his office, etc. Nevertheless, the representation of
reality is adequate to determine some facts about this situation,
enough at least to make him decide not to sell the car.
We shall further assume that the laws of motion determine,
given a situation, all future situations.\footnote{$↑*$}{This
assumption is difficult to reconcile with quantum mechanics,
and relativity tells us that any assignment of simultaneity to events
in different places is arbitrary. However, we are proceeding on the
basis that modern physics is irrelevant to common sense in deciding
what to do, and in particular is irrelevant to solving the `free will
problem'.}
In order to give partial information about situations we
introduce the notion of fluent.
\yskip
\noindent {\bf Fluents}
\yskip
A {\sl fluent} is a function whose domain is the space $Sit$ of
situational. If the range of the function is ($true, false$), then
it is called a $propositional fluent.$ If its range is $Sit$, then it
is called a $situational fluent.$
Fluents are often the values of functions. Thus $raining(x)$
is a fluent such that $raining(x)(s)$ is true if and only
if it is raining at the place $x$ in the situation $s$. We can also
write this assertion as $raining(x,s)$ making use of the well-known
equivalence between a function of two variables and a function of the
first variable whose value is a function of the second variable.
Suppose we wish to assert about a situation $s$ that person
$p$ is in place $x$ and that it is raining in place $x$. We may
write this in several ways each of which has its uses:
\display 35pt:1.: $at(p,x)(s)∧raining (x)(s).$ This corresponds to the
definition given.\par
\display 35pt: 2.: $at(p,x,s)∧raining (x,s).$ This is more conventional
mathematically and a bit shorter.\par
\display 35pt: 3.: $[at(p,x)∧raining (x)](s).$ Here we are introducing a
convention that operators applied to fluents give fluents
whose values are computed by applying the logical
operators to the values of the operand fluents, that is,
if $f$ and $g$ are fluents then
$$(f\hbox{\bf op }g)(s)=f(s)\hbox{\bf op }g(s)$$
\display 35pt: 4.: $[λs↑{\prime}p .at(p,x,s↑{\prime})∧ raining (x,s↑{\prime})](s).$
Here we have
formed the composite fluent by $λ$-abstraction.
\yskip
Here are some examples of fluents and expressions involving them:
\yskip
\display 61pt: 1.: $time(s)$. This is the time associated with the
situation $s$. It is essential to consider time as
dependent on the situation as we shall sometimes wish to
consider several different situations having the same
time value, for example, the results of alternative
courses of actions.
\display 61pt: 2.: $in(x,y,s)$. This asserts that $x$ is in the location
$y$ in situation $s$. The fluent $in$ may be taken as
satisfying a kind of transitive law, namely:
$$∀x . ∀y . ∀z . ∀s . in(x,y,s)∧in(y,z,s) ⊃ in(x,z,s)$$
\display 61pt:{ }: We can also write this law
$$∀x . ∀y . ∀z . ∀ . in(x,y)∧in(y,z) ⊃ in(x,z)$$
\display 61pt: { }: where we have adopted the convention that a quantifier
without a variable is applied to an implicit situation
variable which is the (suppressed) argument of a
propositional fluent that follows. Suppressing situation
arguments in this way corresponds to the natural language
convention of writing sentences like, `John was at home'
or `John is at home' leaving understood the situations to
which these assertions apply.
\display 61pt: 3.: $has(Monkey,Bananas,s)$. Here we introduce the
convention that capitalized words denote proper names,
for example, `Monkey' is the name of a particular
individual. That the individual is a monkey is not
asserted, so that the expression $monkey(Monkey)$ may
have to appear among the premisses of an argument.
Needless to say, the reader has a right to feel that he
has been given a hint that the individual Monkey will
turn out to be a monkey. The above expression is to be
taken as asserting that in the situation $s$ the
individual $Monkey$ has the object $Bananas$. We shall,
in the examples below, sometimes omit premisses such as
$monkey(Monkey)$, but in a complete system they would have
to appear.
\yyskip
\noindent {\bf Causality}
\yskip
\noindent We shall make assertions of causality by means of a fluent $F(π)$
where $π$ is itself a propositional fluent. $F(π,s)$ asserts that
the situation $s$ will be followed (after an unspecified time) by a
situation that satisfies the fluent $π$.
We may use $F$ to assert that if a person is out in the rain
he will get wet, by writing:
$$∀x . ∀p . ∀s . raining(x,s)∧at(p,x,s)∧outside(p,s)
⊃ F(λs↑{\prime}.wet(p,s↑{\prime}),s)$$
\noindent Suppressing explicit mention of situations gives:
$$∀x . ∀p . ∀ raining(x)∧at(p,x)∧outside(p) ⊃ F(wet(p)).$$
\noindent In this case suppressing situations simplifies the statement.
$F$ can also be used to express physical laws. Consider the
law of falling bodies which is often written
\display 61pt: { }: $h=h↓0+v↓0 . (t-t↓0)-{1\over 2}g .(t-t↓0)↑2$
\noindent together with some prose identifying the variables. Since we need a
formal system for machine reasoning we cannot have any prose.
Therefore, we write:
$∀b.∀t.∀s.falling(b,s)∧t≥0∧height(b,s)+velocity(b,s).t-{1\over 2}gt↑2>0$
\display 90pt: { }: $⊃$
$F(λs↑{\prime} . time(s↑{\prime})=time(s)+t ∧ falling(b,s↑{\prime})
∧ height(b,s↑{\prime})=height(b,s)+velocity(b,s) . t-{1\over 2}gt↑2,s)$
\noindent Suppressing explicit mention of situations in this case requires
the introduction of real auxiliary quantities $v,h$ and $\tau$ so that the
sentence takes the following form
$∀b . ∀t . ∀t . ∀v . ∀h.$
$falling(b)∧t≥0∧h=height(b)∧v=velocity(b)∧h+vt-{1\over 2}gt↑2>0$
\display 45pt: { }: $∧time=\tau⊃F(time=t+\tau∧falling(b)∧height=
h+vt-{1\over 2}gt↑2)$
\noindent There has to be a convention (or declarations) so that it is
determined that $height(b), velocity(b)$ and $time$ are fluents,
whereas $t, v, \tau$ and $h$ denote ordinary real numbers.
$F(π,s)$ as introduced here corresponds to A.N. Prior's
(1957, 1968) expression $Fπ$.
The use of situation variables is analogous to the use of
time-instants in the calculi of world-states which Prior (1968) calls
$U$-$T$ calculi. Prior provides many interesting correspondences
between his $U$-$T$ calculi and various axiomatizations of the modal
tense-logics (that is, using this $F$-operator: see part 4)./
However, the situation calculus is richer than any of the
tense-logics Prior considers.
Besides $F$ he introduces three other operators which we also
find useful; we thus have:
\display 35pt: 1.: $F(π,s).$ For some situation $s↑{\prime}$ in the future of
$s,π(s↑{\prime})$ holds.
\display 35pt: 2.: $G(π,s).$ For all situations $s↑{\prime}$ in the future of
$s,π(s↑{\prime})$ holds.
\display 35pt: 3.: $P(π,s).$ For some situations $s↑{\prime}$ in the past of
$s,π(s↑{\prime})$ holds.
\display 35pt: 4.: $H(π,s).$ For all situations $s↑{\prime}$ in the past of
$s,π(s↑{\prime})$ holds.
\noindent It seems also useful to define a situational fluent $next(π)$ as the
next situation $s↑{\prime}$ in the future of $s$ for which $π(s↑{\prime})$
holds. If
there is no such situation, that is, if $¬F(π,s)$, then $next(π,s)$ is
considered undefined. For example, we may translate the sentence `By
the time John gets home, Henry will be home too' as
{\sl at(Henry,home(Henry)next(at(John, home(John)),s)).} Also
the phrase
`when John gets home' translates into {\sl (next(at(John,home(John)),s)).}
Though next $(π,s)$ will never actually be computed since
situations are too rich to be specified completely, the values of
fluents applied to next $(π,s)$ will be computed.
\yyskip
\noindent {\bf Actions}
\yskip
\noindent A fundamental role in our study of actions is played by the
situational fluent
{\sl result}$(p,\sigma,s)$
\noindent Here, $p$ is a person, $\sigma$ is an action or more generally a
strategy, and $s$ is a situation. The value of {\sl result}$(p,\sigma,s)$ is
the situation that results when $p$ carries out $\sigma$, starting in
situation $s$. If the action or strategy does not terminate,
{\sl result}$(p,\sigma,s)$ is considered undefined.
With the aid of {\sl result} we can express certain laws of
ability. For example:
$$has(p,k,s) ∧ fits(k,sf) ∧ at(p,sf,s) ⊃ open(sf,result(p,opens
(sf,k),s))$$
\noindent This formula is to be regarded as an axiom schema asserting that if
in a situation $s$ a person $p$ has a key $k$ that fits the safe
$sf$, then in the situation resulting from his performing the action
$opens(sf,k)$, that is, opening the safe $sf$ with the key $k$, the
safe is open. The assertion $fits(k,sf)$ carries the information
that $k$ is a key and $sf$ a safe. Later we shall be concerned with
combination safes that require $p$ to {\sl know} the combination.
\yyskip
\noindent {\bf Strategies}
\yskip
\noindent Actions can be combined into strategies. The simplest combination is
a finite sequence of actions. We shall combine actions as though
they were ALGOL statements, that is, procedure calls. Thus, the
sequence of actions, (`move the box under the bananas', `climb onto
the box', and `reach for the bananas') may be written:
\e
\d {\bf begin }{\sl move(Box,Under-Bananas); climb(Box);
reach-for (Bananas)}{\bf end};\e
\noindent A strategy in general will be an ALGOL-like compound statement
containing actions written in the form of procedure calling
assignment statements, and conditional {\bf go to's.} We shall not include
any declarations in the program since they can be included in the
much larger collection of declarative sentences that determine the
effect of the strategy.
Consider for example the strategy that consists of walking 17
blocks south, turning right and then walking till you come to
Chestnut Street. This strategy may be written as follows:
\e
\d {\bf begin}\e
\d\ \ \ {\sl face(South)};\e
\d\ \ \ $n=0;$\e
\d $b$:\ \hbox{\bf if }n=17 \hbox{\bf\ then go to }$a$;\e
\d\ \ \ {\sl walk-a-block},$n:=n+1;$\e
\d\ \ \ {\bf go to }$b$;\e
\d $a$:\ \ {\sl turn-right};\e
\d $c$:\ \ {\sl walk-a-block},\e
\d\ \ \ {\bf if }{\sl name-on-street-sign$≠$`Chestnut Street'}
{\bf\ then go to }$c$\e
\d {\bf end};\e
In the above program the external actions are represented by
procedure calls. Variables to which values are assigned have a purely
internal significance (we may even call it mental significance) and
so do the statement labels and the {\bf go} to statements.
For the purpose of applying the mathematical theory of
computation we shall write the program differently: namely, each
occurrence of an action $\alpha$ is to be replaced by an assignment
statement {\sl s:=result}$(p,\alpha,s)$. Thus the above program becomes
\e
\d {\bf begin}\e
\d\ \ \ {\sl s:=result(p,face(South),s)};\e
\d\ \ \ $n:=0$;\e
\d $b$:\ \ \hbox{\bf if }n=17 \hbox{\bf\ then go to }$a$;\e
\d\ \ \ {\sl s:=result(p,walk-a-block,s)};\e
\d\ \ \ $n:=n+1$;\e
\d\ \ \ {\bf go to }$b$;\e
\d $a$:\ \ \{\sl s:=result(p,turn-right,s);}\e
\d $c$:\ \ \{\sl s:=result(p,walk-a-block,s);}\e
\d\ \ \ {\bf if }{\sl name-on-street-sign(s)$≠$`Chestnut Street'}
{\bf\ then go to }$c$.\e
\d {\bf end}\e
Suppose we wish to show that by carrying out this strategy John can
go home provided he is initially at his office. Then according to
the methods of Zohar Manna (1968a, 1968b), we may derive from this
program together with the initial condition {\sl at(John,office
(John)},$s↓0)$ and the final condition $at(John,home(John),s),$ a
sentence $W$ of first-order logic. Proving $W$ will show that the
procedure terminates in a finite number of steps and that when it
terminates $s$ will satisfy $at(John, home(John),s).$
According to Manna`s theory we must prove the following
collection of sentences inconsistent for arbitrary interpretations of
the predicates $q↓1$ and $q↓2$ and the particular interpretations of
the other functions and predicates in the program:
\e
\d $at(John,office(John)s↓0),$\e
\d $q↓1(O,result(John,face(South),s↓0)),$\e
\d $∀n . ∀s . q↓1(n,s) ⊃$\hbox{\bf if }$n=17$\e
\d\ \ \ \ \ \ {\bf then }$q↓2(result(John,walk$-$a$-$block,result
(John,turn$-$right,s)))$\e
\d\ \ \ \ \ \ {\bf else }$q↓1(n+1,result(John,walk$-$a$-$block,s)),$\e
\d $∀s . q↓2(s) ⊃$\hbox{\bf if }$name$-$on$-$street$-$sign(s)≠`Chestnut Street'$\e
\d\ \ \ {\bf then }$q↓2(result(John,walk$-$a$-$block,s))$\e
\d\ \ \ {\bf else }$¬at(John,home(John),s)$\e
Therefore the formula that has to be proved may be written
\e
\d $∃s↓0\{at(John,office(John),s↓0∧q↓1(O,result(John,face
(South),s↓0))\}$\e
\d\ \ \ $⊃$\e
\d $∃n . ∃s . \{q↓1(n,s) ∧${\bf if }$n=17$\e
\d\ \ \ \ \ \ {\bf then }$ ∧ q↓2(result(John,walk$-$a$-$block,result
(John,turn$-$right,s)))$\e
\d\ \ \ \ \ \ {\bf else }$¬q↓1(n+1,result(John,walk$-$a$-$block,s))\}$\e
\d\ \ \ $∨$\e
\d $∃s . \{q↓2(s) ∧${\bf if }$name$-$on$-$street$-$sign(s)≠`Chestnut Street'$\e
\d\ \ \ {\bf then }$¬q↓2(result(John,walk$-$a$-$block,s))$\e
\d\ \ \ {\bf else }$at(John,home(John),s)\}$\e
\noindent In order to prove this sentence we would have to use the following
kinds of facts expressed as sentences or sentence schemas of
first-order logic:
\display 35pt: 1.: Facts of geography. The initial street stretches at
least 17 blocks to the south, and intersects a street
which in turn intersects Chestnut Street a number of
blocks to the right; the location of John's home and
office.
\display 35pt: 2.: The fact that the fluent name-on-street-sign will have
the value `Chestnut Street' at that point.
\display 35pt: 3.: Facts giving the effects of action $\alpha$ expressed as
predicates about $result(p,\alpha,s)$ deducible from sentences
about $s$.
\display 35pt: 4.: An axiom schema of induction that allows us to deduce
that the loop of walking 17 blocks will terminate.
\display 35pt: 5.: A fact that says that Chestnut Street is a finite number
of blocks to the right after going 17 blocks south. This
fact has nothing to do with the possibility of walking.
It may also have to be expressed as a sentence schema or
even as a sentence of second-order logic.
\noindent When we consider making a computer carry out the strategy, we must
distinguish the variable $s$ from the other variables in the second
form of the program. The other variables are stored in the memory of
the computer and the assignments may be executed in the normal way.
The variable $s$ represents the state of the world and the computer
makes an assignment to it by performing an action. Likewise the
fluent name-on-street-sign requires an action, of observation.
\yyskip
\noindent {\bf Knowledge and ability}
\yskip
\noindent In order to discuss the role of knowledge in one's ability to achieve
goals let us return to the example of the safe. There we had
\display 35pt: 1.: $has(p,k,s) ∧ fits(k,sf) ∧ at(p,sf,s) ⊃ open(sf,result(p,
opens(sf,k),s)),$
\noindent which expressed sufficient conditions for the ability of a person to
open a safe with a key. Now suppose we have a combination safe with
a combination $c$. Then we may write:
\display 35pt: 2.: $fits2(c,sf) ∧ at(p,sf,s) ⊃ open(sf,result(p,opens2
(sf,c),s)).$
\noindent where we have used the predicate $fits2$ and the action $opens2$
to express the distinction between a key fitting a safe and a
combination fitting it, and also the distinction between the acts of
opening a safe with a key and a combination. In particular,
$opens2(sf,c)$ is the act of manipulating the safe in accordance with
the combination $c$. We have left out a sentence of the form
$has2(p,c,s)$ for two reasons. In the first place, it is
unnecessary: if you manipulate a safe in accordance with its
combination it will open; there is no need to have anything. In the
second place it is not clear what $has2(p,c,s)$ means. Suppose, for
example, that the combination of a particular safe $sf$ is the number
34125, then $fits$(34125, $sf)$ makes sense and so does the act
$opens2(sf,34125).$ (We assume that $open(sf,result
(p,opens2(sf,34111),s))$ would not be true.) But what could
$has(p,34125,s)$ mean? Thus, a direct parallel between the rules for
opening a safe with a key and opening it with a combination seems
impossible.
Nevertheless, we need some way of expressing the fact that
one has to know the combination of a safe in order to open it.
First we introduce the function $combination(sf)$ and rewrite 2 as
\display 35pt: 3.: $at(p,sf,s) ∧ csafe(sf) ⊃ open(sf,result(p,opens2
sf,combination(sf),s)))$
\noindent where $csafe(sf)$ asserts that $sf$ is a combination safe and
$combination (sf)$ denotes the combination of $sf$. (We could not
write $(sf)$ in the other case unless we wished to restrict ourselves
to the case of safes with only one key.)
Next we introduce the notion of a feasible strategy for a
person. The idea is that a strategy that would achieve a certain goal
might not be feasible for a person because he lacks certain knowledge
or abilities.
Our first approach is to regard the action
$opens2(sf,combination (sf))$ as infeasible because $p$ might not
know the combination. Therefore, we introduce a new function
$idea$-$of$-$combination(p,sf,s)$ which stands for person $p$'s idea of
the combination of $sf$ in situation $s$. The action
$opens2(sf,idea$-$of$-$combination(p,sf,s))$ is regarded as feasible for
$p$, since $p$ is assumed to know his idea of the combination if this
is defined. However, we leave sentence 3 as it is so we cannot yet
prove $open(sf, result(p,opens2(sf,idea$-$of$-$combination(p,sf,s)),s)).$
The assertion that $p$ knows the combination of $sf$ can now be
expressed as
5. $idea$-$of$-$combination(p,sf,s)=combination(sf)$
\noindent and with this, the possibility of opening the safe can be proved.
Another example of this approach is given by the following
formalization of getting into conversation with someone by looking up
his number in the telephone book and then dialing it.
The strategy for $p$ in the first form is
\e
\d {\bf begin}\e
\d\ \ \ $lookup(q,Phone$-$book);$\e
\d\ \ \ $dial(idea$-$of$-$phone$-$number(sq,p))$\e
\d {\bf end;}\e
\noindent or in the second form
\e
\d {\bf begin}\e
\d\ \ \ $s:=result(p,lookup(q,Phone$-$book),s↓0);$\e
\d\ \ \ $s:=result(p,dial(idea$-$of$-$phone$-$number(q,p,s)),s)$\e
\d {\bf end;}\e
\noindent The premisses to write down appear to be
\display 35pt: 1.: $has(p,Phone$-$book,s↓0)$
\display 35pt: 2.: $listed(q,Phone$-$book,s↓0)$
\display 35pt: 3.: $∀s . ∀p . ∀q . has(p,Phone$-$book,s) ∧ listed(q,
Phone$-$book,s) ⊃ phone$-$number(q)=idea$-$of$-$phone$-$number
(p,q,result(p,lookup(q,Phone$-$book),s))$
\display 35pt: 4.: $∀s . ∀p . ∀q . ∀x . at(q,home(q),s) ∧ has(p,x,s)
∧ telephone(x) ⊃ in$-$conversation(p,q,result(p,dial
(phone$-$number(q)),s))$
\display 35pt: 5.: $at(q,home(q),s↓0)$
\display 35pt: 6.: $telephone(Telephone)$
\display 35pt: 7.: $has(p,Telephone,s↓0)$
\noindent Unfortunately, these premisses are not sufficient to allow one to
conclude that
$in$-$conversation(p,q,result(p,$\hbox{\bf begin }$lookup(q,Phone$-$book); dial
(idea$-$of$-$phone$-$number(q,p))$\hbox{\bf end };,$s↓0)).$
\noindent The trouble is that one cannot show that the fluents $at(q,home(q))$
and $has(p,Telephone)$ still apply to the situation $result(p,lookup
(q, Phone$-$book),s↓0).$ To make it come out right we shall revise the
third hypothesis to read:
\display 35pt: { } : $∀s . ∀p . ∀q . ∀x . ∀y . at(q,y,s) ∧ has(p,x,s) ∧ has(p,Phone
$-$book,s) ∧ listed(q,Phone$-$book) ⊃ [\upsilon r.at(q,y,r) ∧ has(p,x,r) ∧
phone$-$number(q)=idea$-$of$-$phone$-$number(p,q,r)](result(p,lookup
(q,Phone$-$book),s)).$
\noindent This works, but the additional hypotheses about what remains
unchanged when $p$ looks up a telephone number are quite {\sl ad hoc.} We
shall treat this problem in a later section.
The present approach has a major technical advantage for
which, however, we pay a high price. The advantage is that we
preserve the ability to replace any expression by an equal one in any
expression of our language. Thus if {\sl phone-number(John)=3217580},
any true statement of our language that contains 3217580 or
{\sl phone-number(John)} will remain true if we replace one by the other.
This desirable property is termed referential transparency.
The price we pay for referential transparency is that we have
to introduce $idea$-$of$-$phone$-$number(p,q,s)$ as a separate {\sl ad hoc}
entity and cannot use the more natural $idea$-$of(p,phone$-$number(q),s)$
where $idea$-$of(p,\phi,s)$ is some kind of operator applicable to the
concept $\phi$. Namely, the sentence $idea$-$of(p,phone$-$number
(q),s)=phone$-$number(q)$ would be supposed to express that $p$ knows
$q$'s phone$-$number, but $idea$-$of(p,3217580,s)=3217580$ expresses only
that $p$ understands that number. Yet with transparency and the
fact that $phone$-$number(q)=3217580$ we could derive the former
statement from the latter.
A further consequence of our approach is that feasibility of
a strategy is a referentially opaque concept since a strategy
containing $idea$-$of$-$phone$-$number(p,q,s)$ is regarded as feasible
while one containing $phone$-$number(q)$ is not, even though these
quantities may be equal in a particular case. Even so, our language
is still referentially transparent since feasibility is a concept of
the metalanguage.
A classical poser for the reader who wants to solve these
difficulties to ponder is, `George IV wondered whether the author of
the Waverly novels was Walter Scott' and `Walter Scott is the author
of the Waverly novels', from which we do not wish to deduce, `George
IV wondered whether Walter Scott was Walter Scott'. This example and
others are discussed in the first chapter of Church's {\sl Introduction
to Mathematical Logic} (1956).
In the long run it seems that we shall have to use a
formalism with referential opacity and formulate precisely the
necessary restrictions on replacement of equals by equals; the
program must be able to reason about the feasibility of its
strategies, and users of natural language handle referential opacity
without disaster. In part 4 we give a brief account of the partly
successful approach to problems of referential opacity in modal logic.
\yyskip
\display 35pt: 3.:{\bf REMARKS AND OPEN PROBLEMS}
\yskip
\noindent The formalism presented in part 2 is, we think, an advance on
previous attempts, but it is far from epistemological adequacy. In
the following sections we discuss a number of problems that it
raises. For some of them we have proposals that might lead to
solutions.
\yyskip
\noindent {\bf The approximate character of $result(p,\sigma,s)$.}
\yskip
\noindent Using the situational fluent $result(p,\sigma,s)$ in formulating the
conditions under which strategies have given effects has two
advantages over the $can(p,\pi,s)$ of part 1. It permits more compact
and transparent sentences, and it lends itself to the application of
the mathematical theory of computation to prove that certain
strategies achieve certain goals.
However, we must recognize that it is only an approximation
to say that an action, other than that which will actually occur,
leads to a definite situation. Thus if someone is asked, `How would
you feel tonight if you challenged him to a duel tomorrow morning and
he accepted?' he might well reply, `I can't imagine the mental state
in which I would do it; if the words inexplicably popped out of my
mouth as though my voice were under someone else's control that would
be one thing; if you gave me a longlasting belligerence drug that
would be another.'
From this we see that $result(p,\sigma,s)$ should not be regarded
as being defined in the world itself, but only in certain
representations of the world; albeit in representations that may have
a preferred character as discussed in part 1.
We regard this as a blemish on the smoothness of
interpretation of the formalism, which may also lead to difficulties
in the formal development. Perhaps another device can be found which
has the advantages of {\sl result} without the disadvantages.
\yyskip
\noindent {\bf Possible meanings of `can'} for a computer program}
\yskip
\noindent A computer program can readily be given much more powerful means of
introspection than a person has, for we may make it inspect the whole
of its memory including program and data to answer certain
introspective questions, and it can even simulate (slowly) what it
would do with given initial data. It is interesting to list various
notions of $can(Program,\pi)$ for a program
\display 35pt: 1.: There is a sub-program $\sigma$ and room for it in memory
which would achieve $\pi$ if it were in memory, and control
were transferred to $\sigma$. No assertion is made that
{\sl Program} knows $\sigma$ or even knows that $\sigma$ exists.
\display 35pt: 2.: $\sigma$ exists as above and that $\sigma$ will achieve
$\pi$ follows from information in memory according to a proof
that {\sl Program} is capable of checking.
\display 35pt: 3.: {\sl Program's} standard problem-solving procedure will find
$\sigma$ if achieving $\pi$ is ever accepted as a subgoal.
\yyskip
\noindent {\bf The frame problem}
\yskip
In the last section of part 2, in proving that one person could get
into conversation with another, we were obliged to add the hypothesis
that if a person has a telephone he still has it after looking up a
number in the telephone book. If we had a number of actions to be
performed in sequence we would have quite a number of conditions to
write down that certain actions do not change the values of certain fluents.
In fact with $n$ actions and $m$ fluents we might have to write down
$mn$ such conditions.
We see two ways out of this difficulty. The first is to
introduce the notion of frame, like the state vector in McCarthy
(1962). A number of fluents are declared as attached to the frame
and the effect of an action is described by telling which fluents are
changed, all others being presumed unchanged.
This can be formalized by making use of yet more ALGOL
notation, perhaps in a somewhat generalized form. Consider a
strategy in which $p$ performs the action of going from $x$ to $y$.
In the first form of writing strategies we have $go(x,y)$ as a
program step. In the second form we have $s:=result(p,go(x,y),s).$
Now we may write
$location(p):=tryfor(y,x)$
\noindent and the fact that other variables are unchanged by this action
follows from the general properties of assignment statements. Among
the conditions for successful execution of the program will be
sentences that enable us to show that when this statement is
executed, $tryfor(y,x)=y.$ If we were willing to consider that $p$
could go anywhere we could write the assignment statement simply as
$location(p):=y$
The point of using $tryfor$ here is that a program using this simpler
assignment is, on the face of it, not possible to execute, since $p$
may be unable to go to $y$. We may cover this case in the more
complex assignment by agreeing that when $p$ is barred from
$y,tryfor(y,x)=x.$
In general, restrictions on what could appear on the right
side of an assignment to a component of the situation would be
included in the conditions for the feasibility of the strategy.
Since components of the situation that change independently in some
circumstances are dependent in others, it may be worthwhile to make
use of the block structure of ALGOL. We shall not explore this
approach further in this paper.
Another approach to the frame problem may follow from the
methods of the next section; and in part 4 we mention a third
approach which may be useful, although we have not investigated it at
all fully.
\yyskip
\noindent {\bf Formal literatures}
\yskip
In this section we introduce the notion of formal literature which is
to be contrasted with the well-known notion of formal language. We
shall mention some possible applications of this concept in
constructing an epistemologically adequate system.
A formal literature is like a formal language with a history:
we imagine that up to a certain time a certain sequence of sentences
have been said. The literature then determines what sentences may be
said next. The formal definition is as follows.
Let $A$ be a set of potential sentences, for example, the set
of all finite strings in some alphabet. Let {\sl Seq}$(A)$ be the set of
finite sequences of elements of $A$
and let $L$:{\sl Seq}$(A)→\{${\bf true,false}$\}$
be such that if $\sigma\in${\sl Seq}$(A)$ and $L(\sigma)$,
that is $L(\sigma)=${\bf true} and $\sigma↓1$
is an initial segment of $\sigma$ then $L(\sigma↓1)$. The pair $(A,L)$ is termed
a {\sl literature}. The interpretation is that $a↓n$ may be said after
$a↓1,\ldotsm,a↓{n-1}$, provided $L((a↓1,\ldotsm,a↓n))$. We shall also write
$\sigma\in L$ and refer to $\sigma$ as a string of the literature $L$.
From a literature $L$ and a string $\sigma\in L$ we introduce the
derived literature $L↓\sigma$. Namely, $\tau\in L↓\sigma$
if and only if $\sigma\ast\tau\in L$,
where $\sigma\ast\tau$ denotes the concatenation of $\sigma$ and $\tau$.
We shall say that the language $L$ is universal for the class
$\Phi$ of literatures if for every literature $M\in\Phi$ there is a
string $\sigma(M)\in L$ such that $M=L↓{\sigma(M)}$;
that is, $\tau\in M$ if and only if $\sigma(M)\ast\tau\in L$.
We shall call a literature computable if its strings form a
recursively enumerable set. It is easy to see that there is a
computable literature $U↓c$ that is universal with respect to the
set $C$ of computable literatures. Namely, let $e$ be a computable
literature and let $c$ be the representation of the G\"odel number of
the recursively enumerable set of $e$ as a string of elements of $A$.
when, we say $c\ast\tau\in U↓c$ if and only if $\tau\in e$.
It may be more convenient to describe natural languages as
formal literatures than as formal languages: if we allow the
definition of new terms and require that new terms be used in
accordance with their definitions, then we have restrictions on
sentences that depend on what sentences have previously been uttered.
In a programming language, the restriction that an identifier not be
used until it has been declared, and then only consistently with the
declaration, is of this form.
Any natural language may be regarded as universal with
respect to the set of natural languages in the approximate sense that
we might define French in terms of English and then say `From now on
we shall speak only French'.
All the above is purely syntactic. The applications we
envisage to artificial intelligence come from a certain kind of
interpreted literature. We are not able to describe precisely the
class of literatures that may prove useful, only to sketch a class of
examples.
Suppose we have an interpreted language such as first-order
logic perhaps including some modal operators. We introduce three
additional operators: $consistent(\Phi), normally(\Phi),$ and
$probably(\Phi)$. We start with a list of sentences as hypotheses. A
new sentence may be added to a string $\sigma$ of sentences according to
the following rules:
\display 35pt: 1.: Any consequence of sentences of $\sigma$ may be added.
\display 35pt: 2.: If a sentence $\Phi$ is consistent with $\sigma$, then
{\sl consistent}$(\Phi)$ may be added. Of course, this is a
non-computable rule. It may be weakened to say that
{\sl consistent}$(\Phi)$ may be added provided $\Phi$ can be shown to
be consistent with $\sigma$ by some particular proof
procedure.
\display 35pt: 3.: {\sl normally}$(\Phi)$, {\sl consistent}$(\Phi)$
$\vdash$ {\sl probably}$(\Phi)$.
\display 35pt: 4.: $\Phi \vdash$ {\sl probably}$(\Phi)$ is a possible deduction.
\display 35pt: 5.: If $\Phi↓1,\Phi↓2,\ldotsm,\Phi↓n \vdash\Phi$
is a possible deduction then
{\sl probably}$(\Phi↓),\ldotsm,${\sl probably}$(\Phi↓n) \vdash$
{\sl probably}$(\Phi)$ is also a possible deduction.
\noindent The intended application to our formalism is as follows:
In part 2 we considered the example of one person telephoning
another, and in this example we assumed that if $p$ looks up $q's$
phone-number in the book, he will know it, and if he dials the number
he will come into conversation with $q$. It is not hard to think of
possible exceptions to these statements such as:
\display 35pt: 1.: The page with $q's$ number may be torn out.
\display 35pt: 2.: $p$ may be blind.
\display 35pt: 3.: Someone may have deliberately inked out $q's$ number.
\display 35pt: 4.: The telephone company may have made the entry
incorrectly.
\display 35pt: 5.: $q$ may have got the telephone only recently.
\display 35pt: 6.: The phone system may be out of order.
\display 35pt: 7.: $q$ may be incapacitated suddenly.
\noindent For each of these possibilities it is possible to add a term
excluding the difficulty in question to the condition on the result
of performing the action. But we can think of as many additional
difficulties as we wish, so it is impractical to exclude each
difficulty separately.
We hope to get out of this difficulty by writing such
sentences as
$$\eqalign{∀p . ∀q . ∀s . at(q,home(q),s) ⊃ ⊗normally(in$-$conversation(p,q,\cr
⊗\qquad\null result(p,dials(phone$-$number(q)),s)))\cr}$$
\noindent We would then be able to deduce
$probably(in$-$conversation(p,q,result(p,dials(phone$-$number(q)),
s↓0)))$
\noindent provided there were no statements like
$kaput(Phone$-$system,s↓0)$
\noindent and
$$\eqalign{∀s . kaput(Phone$-$system,s) ⊃ ¬ in$-$conversation
(p,q,result(p,⊗dials(phone-\cr
⊗\qquad\null number(q)),s))\cr}$$
\noindent present in the system.
Many of the problems that give rise to the introduction of
frames might be handled in a similar way.
The operators {\sl normally, consistent} and {\sl probably} are all
modal and referentially opaque. We envisage systems in which
{\sl probably}$(\pi)$ and {\sl probably}$(¬\pi)$ and therefore
{\sl probably}({\bf false}) will arise.
Such an event should give rise to a search for a
contradiction.
We hereby warn the reader, if it is not already clear to him,
that these ideas are very tentative and may prove useless, especially
in their present form. However, the problem they are intended to
deal with, namely the impossibility of naming every conceivable thing
that may go wrong, is an important one for artificial intelligence,
and some formalism has to be developed to deal with it.
\yyskip
\noindent {\bf Probabilities}
\yskip
On numerous occasions it has been suggested that the formalism take
uncertainty into account by attaching probabilities to its sentences.
We agree that the formalism will eventually have to allow statements
about the probabilities of events, but attaching probabilities to all
statements has the following objections:
\display 35pt: 1.: It is not clear how to attach probabilities to statements
containing quantifiers in a way that corresponds to the
amount of conviction people have.
\display 35pt: 2.: The information necessary to assign numerical
probabilities is not ordinarily available. Therefore, a
formalism that required numerical probabilities would be
epistemologically inadequate.
\yyskip
\noindent {\bf Parallel processing}
\yskip
Besides describing strategies by ALGOL-like programs we may also want
to describe the laws of change of the situation by such programs. In
doing so we must take into account the fact that many processes are
going on simultaneously and that the single-activity-at-a-time
ALGOL-like programs will have to be replaced by programs in which
processes take place in parallel, in order to get an
epistemologically adequate description. This suggests examining the
so-called simulation languages; but a quick survey indicates that
they are rather restricted in the kinds of processes they allow to
take place in parallel and in the types of interaction allowed.
Moreover, at present there is no developed formalism that allows
proofs of the correctness of parallel programs.
\yyskip
\display 35pt: 4.: DISCUSSION OF LITERATURE
\yskip
The plan for achieving a generally intelligent program outlined in
this paper will clearly be difficult to carry out. Therefore, it is
natural to ask if some simpler scheme will work, and we shall devote
this section to criticising some simpler schemes that have been
proposed.
1. L. Fogel (1966) proposes to evolve intelligent automata
better on tasks of greater and greater complexity. The experiments
described by Fogel involve machines with less than 10 states being
evolved to predict the next symbol of a quite simple sequence. We do
not think this approach has much chance of achieving interesting
results because it seems limited to automata with small numbers of
states, say less than 100, whereas computer programs regarded as
automata have $2↑{10↑5}$ to $2↑{10↑7}$ states. This is a reflection of the
fact that, while the representation of behaviours by finite automata
is metaphysically adequate--in principle every behaviour of which a
human or machine is capable can be so represented--this
representation is not epistemologically adequate; that is, conditions
we might wish to impose on a behaviour, or what is learned from an
experience, are not readily expressible as changes in the state
diagram of an automaton.
2. A number of investigators (Galanter 1956, Pivar and
Finkelstein 1964) have taken the view that intelligence may be
regarded as the ability to predict the future of a sequence from
observation of its past. Presumably, the idea is that the experience
of a person can be regarded as a sequence of discrete events and that
intelligent people can predict the future. Artificial intelligence is
then studied by writing programs to predict sequences formed
according to some simple class of laws (sometimes probabilistic
laws). Again the model is metaphysically adequate but
epistemologically inadequate.
In other words, what we know about the world is divided into
knowledge about many aspects of it, taken separately and with rather
weak interaction. A machine that worked with the undifferentiated
encoding of experience into a sequence would first have to solve the
encoding, a task more difficult than any the sequence extrapolators
are prepared to undertake. Moreover, our knowledge is not usable to
predict exact sequences of experience. Imagine a person who is
correctly predicting the course of a football game he is watching; he
is not predicting each visual sensation (the play of light and
shadow, the exact movements of the players and the crowd). Instead
his prediction is on the level of: team A is getting tired; they
should start to fumble or have their passes intercepted.
3. Friedberg (1958,1959) has experimented with representing
behaviour by a computer program and evolving a program by random
mutations to perform a task. The epistemological inadequacy of the
representation is expressed by the fact that desired changes in
behaviour are often not representable by small changes in the machine
language form of the program. In particular, the effect on a
reasoning program of learning a new fact is not so representable.
4. Newell and Simon worked for a number of years with a
program called the General Problem Solver (Newell {\sl et. al.} 1959,
Newell and Simon 1961). This program represents problems as the
task of transforming one symbolic expression into another using a
fixed set of transformation rules. They succeeded in putting a fair
variety of problems into this form, but for a number of problems the
representation was awkward enough so that GPS could only do small
examples. The task of improving GPS was studied as a GPS task, but we
believe it was finally abandoned. The name, General Problem Solver,
suggests that its authors at one time believed that most problems could
be put in its terms, but their more recent publications have indicated
other points of view.
It is interesting to compare the point of view of the present
paper with that expressed in Newell and Ernst (1965) from which we
quote the second paragraph:
\display 35pt: { }: We may consider a problem solver to be a process that takes a
problem as input and provides (when successful) the solution
as output. The problem consists of the problem statement, or
what is immediately given, and auxiliary information, which
is potentially relevant to the problem but available only as
the result of processing. The problem solver has available
certain methods for attempting to solve the problem. For the
problem solver to be able to work on a problem it must first
transform the problem statement from its external form into
the internal representation. Thus (roughly), the class of
problems the problem solver can convert into its internal
representation determines how broad or general it is, and its
success in obtaining solutions to problems in internal form
determines its power. Whether or not universal, such a
decomposition fits well the structure of present problem
solving programs.
\noindent In a very approximate way their division of the problem solver into
the input program that converts problems into internal representation
and the problem solver proper corresponds to our division into the
epistemological and heuristic parts of the artificial intelligence
problem. The difference is that we are more concerned with the
suitability of the internal representation itself.
Newell (1965) poses the problem of how to get what we call
heuristically adequate representations of problems, and Simon (1966)
discusses the concept of `can' in a way that should be compared with
the present approach.
\yyskip
\noindent {\bf Modal logic}
\yskip
\noindent It is difficult to give a concise definition of modal logic. It was
originally invented by Lewis (1918) in an attempt to avoid the
`paradoxes' of implication (a false proposition implies any
proposition). The idea was to distinguish two sorts of truth:
{\sl necessary} truth and mere {\sl contingent} truth. A contingently true
proposition is one which, though true, could be false. This is
formalized by introducing the modal operator $\pfbox$ (read `necessarily')
which forms propositions from propositions. Then $p$'s being a
necessary truth is expressed by $\pfbox\,p$'s being true. More recently,
modal logic has become a much-used tool for analysing the logic of
such various propositional operators as belief, knowledge and tense.
There are very many possible axiomatizations of the logic of
$\pfbox$ none of which seem more intuitively plausible than many others. A
full account of the main classical systems is given by Feys (1965),
who also includes an excellent bibliography. We shall give here an
axiomatization of a fairly simple modal logic, the system $M$ of Feys-Von
Wright. One adds to any full axiomatiation of propositional calculus the
following:
\display 35pt: { }: $Ax. 1:\pfbox\,p⊃p$
\display 35pt: { }: $Ax.2:\pfbox\,(p⊃p)⊃(\pfbox\,p⊃\pfbox\,q)$
\display 35pt: { }: Rule 1: from $p$ and $p⊃q,\in\,q$
\display 35pt: { }: Rule 2: from $p,\in\pfbox\,p$
\display 35pt: { }: (This axiomatization is due to G\"odel).
\noindent There is also a dual modal operator "P",
defined as $¬\pfbox¬$. Its
intuitive meaning is `possibly': "Pp" is true when $p$ is at least
possible, although $p$ may be in fact false (or true). The reader
will be able to see the intuitive correspondence between "¬Pp-p" is
impossible, and $\pfbox\\,~p-$ that is, $p$, is necessarily false.
$M$ is a fairly weak modal logic. One can strengthen it by
adding axioms, for example, adding $Ax.3: \pfbox p ⊃ \pfbox\pfbox p$
yields the system called $S4$; adding $Ax.4: p ⊃ \pfbox p$ yields
$S5$; and other additions are possible.
However, one can also weaken all the systems in
various ways, for instance by changing $Ax.1$ to
$Ax.1↑\prime$:$\pfbox p ⊃ p$. One
easily sees that $Ax.1$ implies $Ax.1↑\prime$, but the converse is not
true. The systems obtained in this way are known as the {\sl deontic}
versions of the systems. These modifications will be useful later
when we come to consider tense-logics as modal logics.
One should note that the truth or falsity of $\pfbox p$ is not
decided by $p$'s being true. Thus $\pfbox$ is not a truth-functional
operator (unlike the usual logical connectives, for instance) and so
there is no direct way of using truth-tables to analyse propositions
containing modal operators. In fact the decision problem for modal
propositional calculi has been quite nontrivial. It is just this
property which makes modal calculi so useful, as belief, tense, etc.,
when interpreted as propositional operators, are all
nontruthfunctional.
The proliferation of modal propositional calculi, with no
clear means of comparison, we shall call the {\sl first problem} of modal
logic. Other difficulties arise when we consider modal predicate
calculi, that is, when we attempt to introduce quantifiers. This was
first done by Barcan-Marcus (1946).
Unfortunately, all the early attempts at modal predicate
calculi had unintuitive theorems ({\sl see} for instance Kripke 1963a),
and, moreover, all of them met with difficulties connected with the
failure of Leibniz' law of identity, which we shall try to outline.
Leibniz' law is
$L:∀x . ∀y . x=y ⊃ (\Phi(x)≡ \Phi(y))$
where $\Phi$ is any open sentence. Now this law fails in modal
contexts. For instance, consider this instance of $L$:
$L↓1: ∀x . ∀y . x=y ⊃ (\pfbox(x=x)≡ \pfbox(x=y))$
\noindent By rule 2 of $M$ (which is present in almost all modal logics), since
$x=x$ is a theorem, so is $\pfbox (x=x).$ Thus $L↓1$ yields
$L↓2: ∀x . ∀y . x=y ⊃ \pfbox (x=y)$
But, the argument goes, this is counterintuitive. For instance the
morning star is in fact the same individual as the evening star (the
planet Venus). However, they are not {\sl necessarily} equal: one can
easily imagine that they might be distinct. This famous example is
known as the `morning star paradox'.
This and related difficulties compel one to abandon Leibniz'
law in modal predicate calculi, or else to modify the laws of
quantification (so that it is impossible to obtain the undesirable
instances of universal sentences such as $L↓2$). This solves the
purely formal problem, but leads to severe difficulties in
interpreting these calculi, as Quine has urged in several papers (cf.
Quine 1964).
The difficulty is this. A sentence $\Phi(a)$ is usually thought
of as ascribing some property to a certain individual $a$. Now
consider the morning star; clearly, the morning star is necessarily
equal to the morning star. However, the evening star is not
necessarily equal to the morning star. Thus, this one
individual--the planet Venus--both has and does not have the property
of being necessarily equal to the morning star. Even if we abandon
proper names the difficulty does not disappear: for how are we to
interpret a statement like $∃x . ∃y(x=y ∧ \Phi (x) ∧ ¬ \Phi (y))$?
Barcan-Marcus has urged an unconventional reading of the
quantifiers to avoid this problem. The discussion between her and
Quine in Barcan-Marcus (1963) is very illuminating. However, this
raises some difficulties--see Belnap and Dunn (1968)--and the recent
semantic theory of modal logic provides a more satisfactory method of
interpreting modal sentences.
This theory was developed by several authors (Hintikka 1963,
1967a; Kanger 1957; Kripke 1963a, 1963b, 1965), but chiefly by
Kripke. We shall try to give an outline of this theory, but if the
reader finds it inadequate, he should consult Kripke (1963a).
The idea is that modal calculi describe several {\sl possible
worlds} at once, instead of just one. Statements are not assigned a
single truth-value, but rather a spectrum of truth-values, one in each
possible world. Now, a statement is necessary when it is true in
{\sl all} possible worlds--more or less. Actually, in order to get
different modal logics (and even then not all of them) one has to be
a bit more subtle, and have a binary relation on the set of possible
worlds--the alternativeness relation. Then a statement is necessary
in a world when it is true in all alternatives to that world. Now it
turns out that many common axioms of modal propositional logics
correspond directly to conditions of alternativeness. Thus for
instance in the system $M$ above, $Ax.1$ corresponds to the
reflexiveness of the alternativeness relation;
$Ax.3(\pfbox p ⊃ \pfbox\pfbox p)$
corresponds to its transitivity. If we make the alternativeness
relation into an equivalence relation, then this is just like not
having one at all; and it corresponds to the axiom: "Pp⊃NPp".
This semantic theory already provides an answer to the first
problem of modal logic: a rational method is available for
classifying the multitude of propositional modal logics. More
importantly, it also provides an intelligible interpretation for
modal predicate calculi. One has to imagine each possible world as
having a set of individuals and an assignment of individuals to names
of the language. Then each statement takes on its truthvalue in a
world $s$ according to the particular set of individuals and
assignment associated with $s$. Thus, a possible world is an
interpretation of the calculus, in the usual sense.
Now, the failure of Leibniz' law is no longer puzzling, for
in one world the morning star--for instance--may be equal to (the
same individual as) the evening star, but in another the two may be
distinct.
There are still difficulties, both formal--the quantification
rules have to be modified to avoid unintuitive theorems (see Kripke,
1963a, for the details)--and interpretative: it is not obvious what
it means to have the {\sl same} individual existing in {\sl different}
worlds.
It is possible to gain the expressive power of modal logic
without using modal operators by constructing an ordinary
truth-functional logic which describes the multiple-world semantics
of modal logic directly. To do this we give every predicate an extra
argument (the world-variable; or in our terminology the
situation-variable) and instead of writing `$\pfbox\Phi$', we write
$∀t . A(s,t) ⊃ \Phi(t)$,
\noindent where $A$ is the alternativeness relation between situations. Of
course we must provide appropriate axioms for $A$.
The resulting theory will be expressed in the notation of the
situation calculus; the proposition $\Phi$
has become a propositional
fluent $λs.\Phi(s)$, and the `possible worlds' of the modal semantics
are precisely the situations. Notice, however, that the theory we get
is weaker than what would have been obtained by adding modal
operators directly to the situation calculus, for
we can give no translation of assertions such as $\pfbox\pi(s)$, where $s$
is a situation, which this enriched situation calculus would contain.
It is possible, in this way, to reconstruct within the
situation calculus subtheories corresponding to the tense-logics of
Prior and to the knowledge logics of Hintikka, as we shall explain
below. However, there is a qualification here: so far we have only
explained how to translate the propositional modal logics into the
situation calculus. In order to translate quantified modal logic,
with its difficulties of referential opacity, we must complicate the
situation calculus to a degree which makes it rather clumsy. There
is a special predicate on individuals and situation $-exists(i,s)-$
which is regarded as true when $i$ names an individual existing in
the situation $s$. This is necessary because situations may contain
different individuals. Then quantified assertions of the modal
logic are translated according to the following scheme:
$∀x . \Phi(x) → ∀x . exists(x,s) ⊃ \Phi(x,s)$
\noindent where $s$ is the introduced situation variable.
We shall not go into the details of this extra translation in
the examples below, but shall be content to define the translations
of the propositional tense and knowledge logics into the situation
calculus.
\yyskip
\noindent {\bf Logic of knowledge}
\yskip
\noindent The logic of knowledge was first investigated as a modal logic by
Hintikka in his book {\sl Knowledge and belief} (1962). We shall only
describe the knowledge calculus. He introduces the modal operator
{\sl Ka} (read `a knows that'), and its dual {\sl Pa}, defined as
$¬${\sl Ka}$¬$.
The semantics is obtained by the analogous reading of {\ Ka} as: `it is
true in all possible worlds compatible with $a$'s knowledge that'.
The propositional logic of {\sl Ka} (similar to $\pfbox$) turns out to be
$S4$, that is $M+Ax.3$; but there are some complexities over
quantification. (The last chapter of the book contains another
excellent account of the overall problem of quantification in modal
contexts.) This analysis of knowledge has been criticized in various
ways (Chisholm 1963, Follesdal 1967) and Hintikka has replied in
several important papers (1967b, 1967c , 1969). The last paper
contains a review of the different senses of `know' and the extent to
which they have been adequately formalized. It appears that two
senses have resisted capture. First, the idea of `knowing how',
which appears related to our `can'; and secondly, the concept of
with' as opposed to simply knowing {\sl who} a person {\sl is}.
knowing a person (place, etc.) when this means `being acquainted
with' as opposed to simply knowing {\sl who} a person {\sl is}.
In order to translate the (propositional) knowledge calculus
into `situation' language, we introduce a three-place predicate into
the situation calculus termed `shrug'. {\sl Shrug}$(p,s↓1,s↓2)$, where $p$
is a person and $s↓1$ and $s↓2$ are situations, is true when, if $p$ is
in fact in situation $s↓2$, then for all he knows he might be in
situation $s↓1$. That is to say, $s↓1$ is an {\sl epistemic alternative}
to $s↓2$, as far as the individual $p$ is concerned--this is
Hintikka's term for his alternative worlds (he calls them model-sets).
Then we translate $K↓pq$, where $q$ is a proposition of
Hintikka's calculus, as $∀t . shrug(p,t,s) ⊃ q(t)$, where $λs.q(s)$
is the fluent which translates $q$. Of course we have to supply
axioms for { \sl shrug}, and in fact so far as the pure knowledge-calculus
is concerned, the only two necessary are
$K1: ∀s . ∀p . shrug(p,s,s)$
\noindent and
$K2: ∀p . ∀s . ∀t .∀r . (shrug(p,t,s) ∧ shrug(p,r,t)) ⊃
shrug(p,r,s)$
\noindent that is, reflexivity and transitivity.
Others of course may be needed when we add tenses and other
machinery to the situation calculus, in order to relate knowledge to
them.
\yyskip
\noindent {\bf Tense logics}
\yskip
\noindent This is one of the largest and most active areas of philosophic
logic. Prior`s book {\sl Past, present and future} (1968) is an
extremely thorough and lucid account of what has been done in the
field. We have already mentioned the four propositional operators
{\sl F, G, P, H} which Prior discusses. He regards these as modal
operators; then the alternativeness relation of the semantic theory
is simply the time-ordering relation. Various axiomatizations are
given, corresponding to deterministic and nondeterministic tenses,
ending and nonending times, etc; and the problems of quantification
turn up again here with renewed intensity. To attempt a summary of
Prior`s book is a hopeless task, and we simply urge the reader to
consult it. More recently several papers have appeared (see, for
instance, Bull 1968) which illustrate the technical sophistication
tense-logic has reached, in that full completeness proofs for various
axiom systems are now available.
As indicated above, the situation calculus contains a
tense-logic (or rather several tense-logics), in that we can define
Prior's four operators in our system and by suitable axioms
reconstruct various axiomatizations of these four operators (in
particular, all the axioms in Bull (1968) can be translated into the
situation calculus).
Only one extra nonlogical predicate is necessary to do this:
it is a binary predicate of situations called {\sl cohistorical}, and is
intuitively meant to assert of its arguments that one is in the
other's future. This is necessary because we want to consider some
pairs of situations as being not temporally related at all. We now
define $F$ (for instance) thus:
$F(π,s) ≡ ∃t$.$cohistorical(t,s) ∧ time(t)>time(s) ∧ π(t).$
\noindent The other operators are defined analogously.
Of course we have to supply axioms for `cohistorical' and
time: this is not difficult. For instance, consider one of Bull's
axioms, say $G↓p⊃GG↓p$, which is better (for us) expressed in the form
$FF↓p⊃F↓p$. Using the definition, this translates into:
$(∃t$.$cohistorical(t,s) ∧ time(t) > time(s) ∧ ∃r$.$
cohistorical(r,t)$
$∧ time(r) > time(t) ∧ π(r)) ⊃ (∃r$.$cohistorical(r,s)$
$∧time(r) > time(s) ∧ π(r))$
\noindent which simplifies (using the transitivity of `$>$') to
$∀t$.$∀r$.$(cohistorical(r,t) ∧ cohistorical(t,s)) ⊃
cohistorical(r,s)$
\noindent that is, the transitivity of `cohistorical'. This axiom is precisely
analogous to the $S4$ axiom $\pfbox p⊃ \pfbox\pfbox p$,
which corresponded to
transitivity of the alternativeness relation in the modal semantics.
Bull's other axioms translate into conditions on `cohistorical' and
time in a similar way; we shall not bother here with the rather
tedious details.
Rather more interesting would be axioms relating `shrug' to
`cohistorical' and time; unfortunately we have been unable to think
of any intuitively plausible ones. Thus, if two situations are
epistemic alternatives (that is, {\sl shrug}$(p,s↓1,s↓2))$ then they may or
may not have the same time value (since we want to allow that $p$ may
not know what the time is), and they may or may not be cohistorical.
\yyskip
\noindent {\bf Logics and theories of actions}
\yskip
\noindent The most fully developed theory in this area is von Wright's action
logic described in his book {\sl Norm and Action} (1963). Von Wright
builds his logic on a rather unusual tense-logic of his own. The
basis is a binary modal connective $T$, so that $pTq$, where $p$ and
$q$ are propositions, means $`p,then\,q'$. Thus the action, for
instance, of opening the window is: {\sl (the window is closed)}$T${\sl (the
window is open)}. The formal development of the calculus was taken a
long way in the book cited above, but some problems of interpretation
remained as Casta{\s n}eda points out in his review (1965). In a more
recent paper von Wright (1967) has altered and extended his formalism
so as to answer these and other criticisms, and also has provided a
sort of semantic theory based on the notion of a life-tree.
We know of no other attempts at constructing a single theory
of actions which have reached such a degree of development, but there
are several discussions of difficulties and surveys which seem
important. Rescher (1967) discusses several topics very neatly, and
Davidson (1967) also makes some cogent points. Davidson's main
thesis is that, in order to translate statements involving actions
into the predicate calculus, it appears necessary to allow actions as
values of bound variables, that is (by Quine's test) as real
individuals. The situation calculus of course follows this advice in
that we allow quantification over strategies, which have actions as a
special case. Also important are Simon's papers (1965, 1967) on
command-logics. Simon's main purpose is to show that a special logic
of commands is unnecessary, ordinary logic serving as the only
deductive machinery; but this need not detain us here. He makes
several points, most notably perhaps that agents are most of the time
not performing actions, and that in fact they only stir to action
when forced to by some outside interference. He has the particularly
interesting example of a serial processor operating in a
parallel-demand environment, and the resulting need for interrupts.
Action logics such as von Wright's and ours do not distinguish
between action and inaction, and we are not aware of any action-logic
which has reached a stage of sophistication adequate to meet Simon's
implied criticism.
There is a large body of purely philosophical writings on
action, time, determinism, etc., most of which is irrelevant for
present purposes. However, we mention two which have recently
appeared and which seem interesting: a paper by Chisholm (1967) and
another paper by Evans (1967), summarizing the recent discussion on
the distinctions between states, performances and activities.
\yyskip
\noindent {\bf Other topics}
\yskip
\noindent There are two other areas where some analysis of actions has been
necessary: command-logics and logics and theories of obligation. For
the former the best reference is Rescher's book (1966) which has an
excellent bibliography. Note also Simon's counterarguments to some of
Rescher's theses (Simon 1965, 1967). Simon proposes that no special
logic of commands is necessary, commands being analysed in the form
`bring it about that $p$!' for some proposition $p$, or, more
generally, in the form `bring it about that $P(x)$ by changing $x$!',
where $x$ is a {\sl command} variable, that is, under the agent's
control. The translations between commands and statements take place
only in the context of a `complete model', which specifies
environmental constraints and defines the command variables. Rescher
argues that these schemas for commands are inadequate to handle the
{\sl conditional command} `when $p$, do $q$', which becomes `bring it
about that $(p⊃q)$!': this, unlike the former, is satisfied by making
$p$ false.
There are many papers on the logic of obligation and
permission. Von Wright's work is oriented in this direction;
Casta{\s n}eda has many papers on the subject and Anderson also has
written extensively (his early influential report (1956) is
especially worth reading). The review pages of the {\sl Journal of
Symbolic Logic} provide many other references. Until fairly recently
these theories did not seem of very much relevance to logics of
action, but in their new maturity they are beginning to be so.
\yyskip
\noindent {\sl Counterfactuals}
\yskip
\noindent There is, of course, a large literature on this ancient philosophical
problem, almost none of which seems directly relevant to us.
However, there is one recent theory, developed by Rescher (1964),
which may be of use. Rescher's book is so clearly written that we
shall not attempt a description of his theory here. The reader
should be aware of Sosa's critical review (1967) which suggests some
minor alterations.
The importance of this theory for us is that it suggests an
alternative approach to the difficulty which we have referred to as
the frame problem. In outline, this is as follows. One assumes, as
a rule of procedure (or perhaps as a rule of inference), that when
actions are performed, {\sl all} propositional fluents which applied to the
previous situation also apply to the new situation. This will often yield
an inconsistent set of statements about the new situation; Rescher's
theory provides a mechanism for restoring consistency in a rational way,
and giving as a by-product those fluents which change in value as a
result of performing the action. However, we have not investigated this
in detail.
\yyskip
\noindent {\bf The communication process}
\yskip
\noindent We have not considered the problems of formally describing the
process of communication in this paper, but it seems clear that they
will have to be tackled eventually. Philosophical logicians have
been spontaneously active here. The major work is Harrah's book
(1963); Cresswell has written several papers on `the logic of
interrogatives', see for instance Cresswell (1965). Among other
authors we may mention Aqvist (1965) and Belnap (1963); again the
review pages of the {\sl Journal of Symbolic Logic} will provide other
references.
\yyskip
\noindent {\bf Acknowledgements}
\yskip
\noindent The research reported here was supported in part by the Advanced
Research Projects Agency of the Office of the Secretary of Defense
(SD-183), and in part by the Science Research Council (B/SR/2299)
\yyskip
{\bf REFERENCES}
\yskip
\bib {{\bf Anderson, A.R. (1956)} The formal analysis of normative systems.
Reprinted in {\sl The Logic of decision and action} (ed. Rescher,
N.). Pittsburgh: University of Pittsburgh Press.}
\bib {{\bf Aqvist, L. (1965)} {\sl A new approach to the logical theory of
interrogatives, part I.} Uppsala: Uppsala Philosophical
Association.}
\bib {{\bf Barcan-Marcus, R.C. (1946)} A functional calculus of the first order
based on strict implication. {\sl Journal of Symbolic Logic}, {\bf 11},
1-16.}
\bib {{\bf Barcan-Marcus, R.C. (1963)} Modalities and intensional languages.
{\sl Boston studies in the Philosophy of Science.} (ed.
Wartofsky, W.). Dordrecht, Holland.}
\bib {{\bf Belnap, N.D. (1963)} {\sl An analysis of questions.} Santa Monica.}
\bib {{\bf Belnap, N.D. and Dunn, J.M. (1968)} The substitution interpretation of
the quantifiers. {\sl Nous},{\bf 2}, 177-85.}
\bib {{\bf Bull, R.A. (1968)} An algebraic study of tense logics with linear
time. {\sl Journal of Symbolic Logic},{\bf 33}, 27-39.}
\bib {{\bf Castaneda, H.N. (1965)} The logic of change, action and norms.
{\sl Journal of Philosophy}, {\bf 62}, 333-4.}
\bib {{\bf Chisholm, R.M. (1963)} The logic of knowing. {\sl Journal of
Philosophy}, {\bf 60}, 773-95.}
\bib {{\bf Chisholm, R.M. (1967)} He could have done otherwise. {\sl Journal
of Philosophy}, {\bf 64}, 409-17.}
\bib {{\bf Church, A. (1956)} {\sl Introduction to Mathematical Logic.} Princeton:
Princeton University Press.}
\bib {{\bf Cresswell, M.J. (1965)}The logic of interrogatives. {\sl Formal systems
and recursive functions.} (ed. Crossley, J.M. and Dummett,
M.A.E.). Amsterdam: North-Holland.}
\bib {{\bf Davidson, D. (1967)} The logical form of action sentences. {\sl The
logic of decision and action.} (ed. Rescher, N.). Pittsburgh:
University of Pittsburgh Press.}
\bib {{\bf Evans, C.O. (1967)} States, activities and performances.
{\sl Australasian Journal of Philosophy},{\bf 45}, 293-308.}
\bib {{\bf Feys, R. (1965)} {\sl Modal Logics.} (ed. Dopp, J.). Louvain: Coll. de
Logique Math. serie B.}
\bib {{\bf Fogel, L.J., Owens, A.J. and Walsh, M.J. (1966)} {\sl Artificial
Intelligence through simulated evolution.} New York: John
Wiley.}
\bib {{\bf Follesdal, D. (1967)} Knowledge, identity and existence.
{\sl Theoria}, {\bf 33}, 1-27.}
\bib {{\bf Friedberg, R.M. (1958)} A learning machine, part I.
{\sl IBM J. Res. Dev.}, {\bf 2}, 2-13.}
\bib {{\bf Friedberg, R.M., Dunham, B., and North, J.H. (1959)} A learning
machine, part II. {\sl IBM J. Res. Dev.},{\bf 3}, 282-7.}
\bib {{\bf Galanter, E. and Gerstenhaber, M. (1956)} On thought: the extrinsic
theory. {\sl Psychological Review},{\bf 63}, 218-27.}
\bib {{\bf Green, C. (1969)} Theorem-proving by resolution as a basis for
question-answering systems. {\sl Machine Intelligence 4,} pp.
183-205 (eds. Meltzer, B. and Michie, D.). Edinburgh:
Edinburgh University Press.}
\bib {{\bf Harrah, D. (1963)} {\sl Communication: a logical model.} Cambridge,
Massachusetts: MIT Press.}
\bib {{\bf Hintikka, J. (1962)} {\sl Knowledge and belief: an introduction
to the logic of two notions.} New York: Cornell University Press.}
\bib {{\bf Hintikka, J. (1963)} The modes of modality. {\sl Acta
Philosophica Fennica}, {\bf 16}, 65-82.}
\bib {{\bf Hintikka, J. (1967a)} A program and a set of concepts for
philosophical logic. {\sl The Monist,} {\bf 51}, 69-72.}
\bib {{\bf Hintikka, J. (1967b)} Existence and identity in epistemic contexts.
{\sl Theoria}, {\bf 32}, 138-47.}
\bib {{\bf Hintikka, J. (1967c)} Individuals, possible worlds and epistemic
logic. {\sl Nous,} {\bf 1}, 33-62.}
\bib {{\bf Hintikka, J. (1969)} Alternative constructions in terms of the basic
epistemological attitudes. {\sl Contemporary philosophy in
Scandinavia} (ed. Olsen, R.E.) (to appear).}
\bib {{\bf Kanger, S. (1957)} A note on quantification and modalities.
{\sl Theoria} {\bf 23}, 133-4.}
\bib {{\bf Kripke, S. (1963a)} Semantical considerations on modal logic.
{\sl Acta Philosophica Fennica,} {\bf 16}, 83-94.}
\bib {{\bf Kripke, S. (1963b)} Semantical analysis of modal logic I.
{\sl Zeitschrift fur math. Logik und Grundlagen der Mathematik,}
{\bf 9}, 67,96.}
\bib {{\bf Kripke, S. (1965)} Semantical analysis of modal logic II.
{\sl The theory of models} (eds. Addison, Henkin and Tarski).
Amsterdam, North-Holland.}
\bib {{\bf Lewis, C.I. (1918)} {\sl A survey of symbolic logic.} Berkeley:
University of California Press.}
\bib {{\bf Manna, Z. (1968a)} {\sl Termination of algorithms.} Ph.D. Thesis,
Carnegie-Mellon University.}
\bib {{\bf Manna, Z. (1968b)} {\l Formalization of properties of programs} Stanford
Artificial Intelligence Report: Project Memo AI-64.}
\bib {{\bf McCarthy, J. (1959)} Programs with common sense. {\sl Mechanization of
thought processes,} Vol. I. London: HMSO.}
\bib {{\bf McCarthy, J. (1962)} Towards a mathematical science of computation.
{\sl Proc. IFIP Congress 62.} Amsterdam: North-Holland Press.}
\bib {{\bf McCarthy, J. (1963)} {\sl Situations, actions and causal laws.}
Stanford Artificial Intelligence Project: Memo 2.}
\bib {{\bf Minsky, M. (1961)} Steps towards artificial intelligence.
{\sl Proceedings of the I.R.E.,} {\bf 49}, 8-30.}
\bib {{\bf Newell, A., Shaw, V.C. and Simon, H.A. (1959)} Report on a general
problem-solving program. {\sl Proceedings ICIP.} Paris:UNESCO
House.}
\bib {{\bf Newell, A. and Simon, H.A. (1961)} GPS - a program that simulates
human problem-solving. {\sl Proceedings of a conference in
learning automata.} Munich:Oldenbourgh.}
\bib {{\bf Newell, A. (1965)} Limitations of the current stock of ideas about
problem-solving. {\sl Proceedings of a conference on Electronic
Information Handling,} pp. 195-208 (eds. Kent, A. and
Taulbee, O.). New York: Spartan.}
\bib {{\bf Newell, A. & Ernst, C. (1965)} The search for generality.
{\sl Proc. IFIP Congress 65}}
\bib {{\bf Pivar, M. & Finkelstein, M. (1964)} {\sl The Programming Language
LISP: its operation and applications} (eds. Berkely, E.C. & Bobrow,
D.G.). Cambridge, Massachusetts: MIT Press.}
\bib {{\bf Prior, A.N. (1957)} {\sl Time and modality.} Oxford: Clarendon Press.}
\bib {{\bf Prior, A.N. (1968)} {\sl Past, present and future.} Oxford: Clarendon
Press.}
\bib {{\bf Quine, W.V.O. (1964)} Reference and modality. {\sl From a logical
point of view.} Cambridge, Massachusetts: Harvard University Press.}
\bib {{\bf Rescher, N. (1964)} {\sl Hypothetical reasoning.} Amsterdam:
North-Holland.}
\bib {{\bf Rescher, N. (1966)} {\sl The logic of commands.} London: Routledge.}
\bib {{\bf Rescher, N. (1967)} Aspects of action. {\sl The logic of decision
and action} (ed. Rescher, N.). Pittsburgh: University of
Pittsburgh Press.}
\bib {{\bf Shannon, C. (1950)} Programming a computer for playing chess.
{\sl Philosophical Magazine,}{\bf 41}}.
\bib {{\bf Simon, H.A. (1965)} The logic of rational decision. {\sl British
Journal for the Philosophy of Science,} {\bf 16}, 169-86.}
\bib {{\bf Simon, H.A (1966)} {\sl On Reasoning about actions.} Carnegie
Institute of Technology: Complex Information Processing Paper 87.}
\bib {{\bf Simon, H.A. (1967)} The logic of heuristic decision making {\sl The
logic of decision and action} (ed. Rescher, N.). Pittsburgh:
University of Pittsburgh Press.}
\bib {{\bf Sosa, E. (1967)} Hypothetical reasoning. {\sl Journal of Philosophy},
{\bf 64}, 293-305}
\bib {{\bf Turing, A.M. (1950)} Computing machinery and intelligence.
{\sl Mind}, {\bf 59},433-60.}
\bib {{\bf von Wright, C.H. (1963)} {\sl Norm and action: a logical enquiry.}
London: Routledge.}
\bib {{\bf von Wright, C.H. (1967)} The Logic of Action - a sketch. {\sl The
logic of decision and action} (ed. Rescher, N.). Pittsburgh:University
of Pittsburgh Press.}
\vfill \eject
\end